"""
二次“素数生成”多项式

欧拉发现了这个著名的二次多项式：n2 + n + 41。n从0到39，这个二次多项式生成了40个素数。然而，当n = 40时，
402 + 40 + 41 = 40(40 + 1) + 41能够被41整除，同时显然当n = 41时，412 + 41 + 41也能被41整除。
随后，另一个神奇的多项式n2 − 79n + 1601被发现了，对于n从0到79，它生成了80个素数。这个多项式的系数-79和1601的乘积为-126479。

考虑以下形式的二次多项式：n2 + an + b, 满足|a| < 1000且|b| < 1000。其中|n|表示n的绝对值，例如|11| = 11以及|−4| = 4。
这其中存在某个二次多项式能够对从0开始尽可能多的连续整数n都生成素数，求其系数a和b的乘积。
"""
# 思路：n=0可推出b一定是素数，素数除了2以外都是是奇数，所以n=奇数时，若a为偶数，奇数+偶数+b为偶一定不是素数，所以a为奇数
import math
def is_prime(n):
    if n==1 or n==2:
        return True
    else:
        for i in range(2,int(n**0.5)+1):
            if(n%i==0):
                return False
        else:
            return True

def prime_count(a,b):
    n=0
    c=0
    while is_prime(math.fabs(n**2+a*n+b)):
        c+=1
        n+=1
    return c

max_cnt=0
max_ab=[]
max_num=[]
prime_b=[b for b in range(2,1001) if is_prime(b)]
for b in prime_b:
    for a in [x-b-1 for x in prime_b]:
        if prime_count(a,b)>max_cnt:
            max_cnt=prime_count(a,b)
            max_num.append([a,b])
            max_ab.append(a*b)
print(max_num[-1])
print(max_ab[-1])



#   优化算法
#   数学思路：n*n+n+41其实从-40到39都能生成素数，所以(n-40)*(n-40)+(n-40)+41，n从0到79都生成素数，展开就是n2 − 79n + 1601
#   所以令n=n-p，带入，用p表示系数a，b，更具绝对值小于1000求限制，p越大，连续越长，求出p为31，正好是结果。
#   但是这是根据欧拉二项式推出来的，逻辑上不是确定解
#   n**2+(1-2*p)*n+p**2-p+41

# import math
# def is_prime(n):
#     if n==1 or n==2:
#         return True
#     else:
#         for i in range(2,int(n**0.5)+1):
#             if(n%i==0):
#                 return False
#         else:
#             return True

# def prime_count(a,b):
#     n=0
#     c=0
#     while is_prime(math.fabs(n**2+a*n+b)):
#         c+=1
#         n+=1
#     return c

# p=-30       # 基于|1-2*p|<=1000 且 |p**2-p+41|<=1000  得出p的范围  -(根号3837+1)/2<=p<=(根号3837+1)/2
# num=0
# max_ab=0
# while p**2-p+41<=1000:
#     if prime_count(1-2*p,p**2-p+41)>num:
#         num=prime_count(1-2*p,p**2-p+41)
#         max_ab=(1-2*p)*(p**2-p+41)
#     p+=1
# print(max_ab)




# def com_pri(number):#判断素数
#     if  number==2:
#         return True
#     else:
#         for i in range(2,int(number**0.5)+1):
#             if number%i==0:
#                 return False
#         return True
# fan_an=[x for x in range(2,1001) if com_pri(x)]#n =0 时， b为素数
# def an_fan(i,j,n, c=0):
#     if com_pri(abs(n**2+i*n+j)):
#          c+=1
#          return an_fan(i,j,n+1,c)
#     else:
#          return c
# number=0
# for j in fan_an:
#     for i in [x-j-1 for x in fan_an]:#n= 1 时， a+b+1 为素数
#         result=an_fan(i,j,0,c=0)
#         if number <= result:
#             number = result
#             ab = [j, i]
# print(ab)
# print(ab[0]*ab[1])
# 答案：-59231


